//
//  Problem590.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/23.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 590. N 叉树的后序遍历
 给定一个 N 叉树，返回其节点值的 后序遍历 。
 N 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

 进阶：递归法很简单，你可以使用迭代法完成此题吗?
 
 示例 1：
                1
            /   |   \
           3    2    4
          / \
         5   6
 输入：root = [1,null,3,2,4,null,5,6]
 输出：[5,6,3,2,4,1]
 
 示例 2：
 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
  

 提示：
     N 叉树的高度小于或等于 1000
     节点总数在范围 [0, 10^4] 内
 */
@objcMembers class Problem590: NSObject {
    func solution() {
        let root = Node(1)
        let fNode = Node(3)
        fNode.children = [Node(5), Node(6)]
        root.children = [fNode, Node(2), Node(4)]
        
        print(postorderBFS(root))
        
    }
    
    /*
     深度 递归
     */
    func postorder(_ root: Node?) -> [Int] {
        if root == nil {
            return []
        }
        
        var list: [Int] = []
        for node in root?.children ?? [] {
            list.append(contentsOf: postorder(node))
        }
        list.append(root!.val)
        return list
    }
    
    /*
     广度 数组
     1：从数组list头部拿取一个node，如果它没有children，那么将他的值放入结果集中
     2: 如果有children，那么先把node再放到list顶部，然后children插入list头部（后续遍历），再将node的children = []（防止再次插入，死循环）

     */
    func postorderBFS(_ root: Node?) -> [Int] {
        if root == nil {
            return []
        }
        
        var nList: [Int] = []
        var list: [Node?] = [root]
        while list.isEmpty == false {
            let node = list.removeFirst()
            if node?.children.count == 0 {
                nList.append(node!.val)
            } else {
                list.insert(node, at: 0)
                list.insert(contentsOf: node?.children ?? [], at: 0)
                node?.children = []
            }
        }
        
        return nList
    }
    
}

/// N叉树
public class Node {
    public var val: Int
    public var children: [Node]
    public init(_ val: Int) {
        self.val = val
        self.children = []
    }
}
